
public class Test0411 {
    public boolean canPartition(int[] nums) {
   	int n=nums.length;
   	int target=0;
   	
       for(int i=0;i<n;i++) {
       	target+=nums[i];
       }
       
       if(target%2==1) {
       	return false;
       }
       target=target/2;
       boolean[][] dp=new boolean[n+1][target+1];
       for(int i=0;i<=n;i++) dp[i][0]=true;
       for(int i=1;i<=n;i++) {
       	for(int j=1;j<=target;j++) {
       		dp[i][j]=dp[i-1][j];
       		if(j-nums[i-1]>=0) dp[i][j]=dp[i][j]||dp[i-1][j-nums[i-1]];
       	}
       }
       return dp[n][target];
   }
}
